/*
day123
2019.12.29
*/
#include<iostream>
using namespace std;

class Solution {
public:
	double help(double x, int n)
	{
		if(n==1) return x;
		double res=x;
		int n1=n/2;
		int n2=n-n1;
		return help(x,n1) * help(x,n2);
	
	}
   
   
    double myPow(double x, int n) {
        if(n==0) return 1;
        if(n>0) return help(x,n);
        return 1/help(x,-1*n);
    }

    
};



class Solution2 {
public:
    double help(double x, int n)
	{
//		cout<<"x="<<x<<'\t'<<"n="<<n<<endl;
		if(n==0) return 1;
		if(n==1) return x;
		
		int cur=1;
		double tem=x;
		
		while(cur<=n/2)
		{
			tem=tem*tem;
			cur=cur+cur;
		}
		
		if(cur<n) return tem*help(x,n-cur);
		
		return tem;
	}
	
	double myPow(double x, int n) 
	{
		if(x==1) return 1;
		
        if(n==0) return 1;
        
        if(n>0) return help(x,n);
        
        return 1/help(x,-1*n);
    }
};



class Solution3 {
public:
    double myPow(double x, int n) {
        if (n == 0) { return 1; }
        if (n == 1) { return x; }
        if (n == -1) { return 1 / x; }
        double half = myPow(x, n / 2);
        double rest = myPow(x, n % 2);
        return rest * half * half;

    }
};
int main()
{
	Solution2 s2;
	cout<<s2.myPow(2.00000,-1)<<endl;
//	1.00000
//-2147483648
	return 0;
}
